/**
 * 给定一个二叉树的前序遍历preorder和中序遍历inoreder 从中构建二叉树
 * 前序遍历[根节点 | 左子树 | 右子树]
 * 中序遍历[左子树 | 根节点 | 右子树]
 */
function TreeNode (data, left, right) {
  this.data = data
  this.left = left
  this.right = right
}
/**
 * 
 * @param {*} preorder 前序遍历
 * @param {*} inorderMap 
 * @param {*} i 当前树的根节点在前序遍历中的索引
 * @param {*} l 子树在中序遍历数组中的左索引；
 * @param {*} r 子树在中序遍历数组中的右索引。
 * @returns 
 */
function dfs (preorder, inorderMap, i, l, r) {
  // 子树区间为空时终止
  if (r - l < 0) return null
  // 初始化根节点
  const root = new TreeNode(preorder[i])
  // 查询根节点在中序遍历的索引
  const m = inorderMap.get(preorder[i]) // 1 0
  // 左子树
  root.left = dfs(preorder, inorderMap, i + 1, l, m - 1)
  // 右子树
  root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r)
  return root
}
function buildTree (preOrder, inorder) {
  // 初始化哈希表
  let inorderMap = new Map()
  for (let i = 0; i < inorder.length; i++) {
    inorderMap.set(inorder[i], i)
  }
  const root = dfs(preOrder, inorderMap, 0, 0, inorder.length - 1)
  return root
}
console.log(buildTree([3, 9, 2, 1, 7], [9, 3, 1, 2, 7]));